package cn.camel.algorithm.tree.heap;

/**
 * @author: Camel
 * @description: 堆排序实现
 * @date: 2025/10/14 13:34
 */
public class HeapSort {

    public static void heapSort(int[] arr) {
        // 计算数组大小
        int n = arr.length;
        // 1. 构建最大堆,从最后一个非叶子节点开始到头节点堆化
        for(int i = n/2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // 2. 排序
        // 2. 逐个提取堆顶元素（最大值）并调整堆
        for (int i = n - 1; i > 0; i--) {
            // 将当前堆顶（最大值）交换到数组末尾
            swap(arr, 0, i);
            // 对剩余元素重新调整成最大堆（堆大小减1）
            heapify(arr, i, 0);
        }
    }

    /**
     * 堆化函数(自顶向下)
     * @param arr 待排序数组
     * @param heapSize 数组大小
     * @param rootIndex 当前指向元素索引
     */
    private static void heapify(int[] arr, int heapSize, int rootIndex) {
        int largest = rootIndex;    // 初始化最大元素为根节点
        int leftChild = 2 * rootIndex + 1;   // 左子节点索引
        int rightChild = 2 * rootIndex + 2;  // 右子节点索引
        // 如果左子节点存在且大于根节点,最大元素索引指向左子节点索引
        if (leftChild < heapSize && arr[leftChild] > arr[largest]) {
            largest = leftChild;
        }
        // 如果左子节点存在且大于根节点,最大元素索引指向右子节点索引
        if (rightChild < heapSize && arr[rightChild] > arr[largest]) {
            largest = rightChild;
        }

        // 如果最大值不是根节点，需要交换并继续调整
        if (largest != rootIndex) {
            swap(arr, rootIndex, largest);
            // 递归调整受影响的子树
            heapify(arr, heapSize, largest);
        }
    }

    // 交换数组中的两个元素
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前数组：");
        printArray(arr);

        heapSort(arr);

        System.out.println("\n排序后数组：");
        printArray(arr);
    }
}
